# ref: http://www.cnblogs.com/skyiv/archive/2005/12/20/Google250.html

def hard_duplicate_remove(sequence):
    """
    1 <= len(sequence) <= 50
    1 <= sequence[i] <= 1000
    
    returns the lexicographically first sequence with duplicates removed
    """
    while True:
        occurrence = {} # stores occurrence of elems

        # count occurrence of each element
        for elem in sequence:
            if elem not in occurrence:
                occurrence[elem] = 0
            occurrence[elem] += 1

        # if each remaining element has no duplicate, exit
        if len(filter(lambda x: x > 1, occurrence.values())) == 0:
            break

        # try remove duplicate
        # insight:
        # if there exists element less than current element and the
        # next duplicate, remove the current element, or remove the
        # duplicate; if no duplicate left, keep the current
        new_sequence = []
        for i in range(len(sequence)):
            elem = sequence[i]

            if elem == -1: # already removed
                continue

            if occurrence[elem] > 1: # duplicate left
                dup_index = sequence.index(elem, i+1) # find next dup
                smaller_exists = False
                for j in range(i, dup_index):
                    if sequence[j] < elem:
                        smaller_exists = True
                        break
                # if smaller exists, do nothing (the current is no longer accessed)
                # if not, keep current and remove next
                if not smaller_exists:
                    new_sequence.append(elem)
                    sequence[dup_index] = -1
                    occurrence[elem] -= 1
            else: # this one must be kept
                new_sequence.append(elem)
            occurrence[elem] -= 1 # decrement element occurrence
        # update sequence
        sequence = new_sequence

    return sequence
